// 解题思路：
// 题目要求：气球在不同的高度上，直径为 [x1, x2]，从 x 轴垂延 y 周的方向射箭，找出引爆所有气球的最小弓箭数
// 经验：根据题目要求，发现这是一道区间题目，区间题目要进行排序
// 贪心策略：找到气球直径重叠的区间，在重叠的区间射箭，尽量引爆更多的气球
// 题目就是找交集，有交集一支箭就可以搞定，没交集还需要一支箭
// 以第一个区间为基准，遍历后面的区间，判断是否有交集，如果有交集，求出交集，作为基准，再判断和后面的是否有交集，一直遍历直到数组结束
// 如果没有交集，就收集一次结果 ret++，直到数组最后一个元素
// 细节：到最后一个元素，并没有收集最后一个结果，因此要单独收集一下 ret++;
// 返回收集的结果即可

import java.util.Arrays;

public class Solution {
    public int findMinArrowShots(int[][] points) {
        Arrays.sort(points, (a, b) -> {
            if(a[0] >= b[0]) return 1;
            else return -1;
        });

        int n = points.length;
        int left = points[0][0]; int right = points[0][1];

        int ret = 0;
        int i = 1;
        while(i < n){
            int a = points[i][0];
            int b = points[i][1];
            if(right >= a){
                left = Math.max(left, a);
                right = Math.min(right, b);
            }else{
                ret++;
                left = a;
                right = b;
            }
            i++;
        }

        return ret + 1;
    }
}
